﻿// 0917train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <bitset>

using namespace std;

/*
小明从糖果盒中随意抓一把糖果，
每次小明会取出一半的糖果分给同学们。
当糖果不能平均分配时，小明可以选择从糖果盒中（假设盒中糖果足够）
取出一个糖果或放回一个糖果
小明最少需要多少次（取出、放回和平均分配均记一次），能将手中糖果分至只剩一颗

输入描述
抓取的糖果数（<10000000000）

输出描述
最少分至一颗糖果的次数

15+1=16
16/2=8
8/2=4
4/2=2
2/2=1
 */
class Solution01
{
public:
    void backTrack(long long num, int count)
    {
        if (num == 1)
        {
            result = min(count, result);
            return;
        }

        if (count > result)
        {
            return;
        }

        if (num%2==0)
        {
            long long next = num / 2;
            int next_count = count + 1;
            backTrack(next, next_count);
        }
        else
        {
            long long next_add = (num + 1) / 2;
            int next_count = count + 2;
            backTrack(next_add, next_count);

            long long next_minus = (num - 1) / 2;
            backTrack(next_minus, next_count);
        }

        //backTrack
    }

    Solution01(long long total)
    {
        if (total==0)
        {
            cout << 0;
            return;
        }
        backTrack(total, 0);
        cout << result;
        //Solution01
    }
private:
    int result = INT_MAX;
};


/*
地图表示为一维数组，数组的索引代表水平位置，数组的高度代表相对海拔高度
其中数组元素 0 代表地面
例如[0,1,2,4,3,1,0,0,1,2,3,1,2,1,0]， 代表如下图所示的地图
地图中有两个山脉位置分别为 1,2,3,4,5和8,9,10,11,12,13，最高峰高度分别为4,3
最高峰位置分别为3,10
一个山脉可能有多座山峰（高度大于相邻位置的高度，或在地图边界且高度大于相邻的高度）

登山时会消耗登山者的体力（整数），
上坡时，消耗相邻高度差两倍的体力，
下坡时消耗相邻高度差一倍的体力，平地不消耗体力，登山者体力消耗到零时会有生命危险。
例如，上图所示的山峰：从索引 0，走到索引 1，高度差为 1，需要消耗 2*1=2 的体力；
从索引 2 高度 2走到高度 4 索引 3 需要消耗 2*2=4 的体力；
从索引 3 走到索引 4 则消耗 1*1=1 的体力

攀登者想要评估一张地图内有多少座山峰可以进行攀登，且可以安全返回到地面，且无生命危险

输入
0,1,4,3,1,0,0,1,2,3,1,2,1,0
11
输出
2

 */
class Solution02
{
public:
    void computeTop(int start, vector<int>&result_top, vector<int>& num_vec, int limit)
    {
        
        //原路出，原路回
        int v_size = num_vec.size();
        int curr_i = start+1;

        int cost = 0;
        while (curr_i<v_size && num_vec[curr_i]>0)
        {
            cost += abs(num_vec[curr_i]-num_vec[curr_i -1]);
            //登山者体力消耗到零时会有生命危险
            if (cost * 3 >= limit)
            {
                break;
            }

            if (curr_i==v_size-1 && num_vec[curr_i]>num_vec[curr_i-1])
            {
                result_top.push_back(curr_i);
                break;
            }

            if (num_vec[curr_i]> num_vec[curr_i - 1] && num_vec[curr_i]> num_vec[curr_i + 1])
            {
                result_top.push_back(curr_i);
            }
            curr_i++;
        }

        //computeTop
    }

    vector<int>getSpace(vector<int>& num_vec)
    {
        vector<int>space_i;
        int v_size = num_vec.size();
        for (int i = 0; i < v_size; i++)
        {
            if (i == v_size - 1) continue;
            if (num_vec[i]==0 && num_vec[i+1]>0)
            {
                space_i.push_back(i);
            }

        }
        return space_i;
    }

    Solution02(vector<int>&num_vec, int limit)
    {
        //0 1 2 3

        //保存平地
        vector<int>space_vec = getSpace(num_vec);

        vector<int>left_top_i;
        for (auto&start:space_vec)
        {
            computeTop(start, left_top_i, num_vec, limit);
        }

        reverse(num_vec.begin(), num_vec.end());

        vector<int>right_pos_i;
        space_vec = getSpace(num_vec);
        for (auto& start : space_vec)
        {
            computeTop(start, right_pos_i, num_vec, limit);
        }

        unordered_set<int>result;
        for (auto&top_i: left_top_i)
        {
            result.insert(top_i);
        }

        int v_size = num_vec.size();
        for (auto&top_i:right_pos_i)
        {
            result.insert(v_size - 1 - top_i);
        }

        cout << result.size();

        //Solution02
    }
    
};


/*
输入
5
1,0,0,0,1
0,0,0,1,1
0,1,0,1,0
1,0,0,1,1
1,0,1,0,1
输出
122

第一行向右整体循环移动1位，得到本行的最大值[1,1,0,0,0]，二进制值为11000，十进制值为24
第二行向右整体循环移动2位，得到本行的最大值[1,1,0,0,0]，二进制值为11000，十进制值为24
第三行向左整体循环移动1位，得到本行的最大值[1,0,1,0,0]，二进制值为10100，十进制值为20
第四行向右整体循环移动2位，得到本行的最大值[1,1,1,0,0]，二进制值为11100，十进制值为28
第五行向右整体循环移动1位，得到本行的最大值[1,1,0,1,0]，二进制值为11010，十进制值为26
 */
class Solution03
{
public:
    int compute(deque<int>&exec_queue)
    {
        int sum = 0;
        int q_size = exec_queue.size();
        for (int i=0; i< q_size; i++)
        {
            int curr = exec_queue[i];
            if (curr==1)
            {
                int para = q_size - 1 - i;
                sum += pow(2, para);
            }
        }
        return sum;
    }

    int getMax(vector<int>&curr_v)
    {
        deque<int>exec_queue;

        int v_size = curr_v.size();
        for (int i=0; i< v_size; i++)
        {
            exec_queue.push_back(curr_v[i]);
        }
        int max_sum = compute(exec_queue);
        
        int count = v_size;
        while (count--)
        {
            int top = exec_queue.front();
            exec_queue.pop_front();
            exec_queue.push_back(top);

            int curr_sum = compute(exec_queue);
            max_sum = max(curr_sum, max_sum);
            //while
        }

        count = v_size;
        while (count--)
        {
            int back = exec_queue.back();
            exec_queue.pop_back();
            exec_queue.push_front(back);

            int curr_sum = compute(exec_queue);
            max_sum = max(curr_sum, max_sum);
            //while
        }

        return max_sum;
	    //getMax
    }

    Solution03(vector<vector<int>>&grid)
    {
        int result = 0;

        for (auto&item:grid)
        {
            int item_max = getMax(item);
            result += item_max;
        }

        cout << result;
        //Solution03
    }
};


class Solution13
{
public:
    int getItemMax(string&row_str)
    {
        int s_size = row_str.size();
        int ring_size = s_size * 2;
        string ring_str = row_str + row_str;

        uint64_t max_sum = 0;
        uint64_t curr_value = 0;

        for (auto&ch:row_str)
        {
            curr_value = (curr_value << 1) | (ch - '0');
        }
        max_sum = curr_value;

        string curr_str = row_str;
        for (int left=1, right=s_size; right<ring_size; left++, right++)
        {
            curr_str = curr_str.substr(1);
            curr_str += ring_str[right];

            uint64_t curr_value = 0;
            for (auto& ch : curr_str)
            {
                curr_value = (curr_value << 1) | (ch - '0');
            }
            max_sum = max(max_sum, curr_value);
        }
        return max_sum;
        //getMax
    }

    Solution13(vector<string>&str_vec)
    {
        int result = 0;
        for (auto&str_item:str_vec)
        {
            int max_sum = getItemMax(str_item);
            result += max_sum;
        }
        cout << result;

    }
};

int main()
{
	{
        //十进制转十六进制
        int num = 128;
        stringstream hex_sstream;
        hex_sstream << hex << num;
        string hex_str = hex_sstream.str();

        //cout << hex_str;
        //十六进制转十进制
        int hex_num = stoi(hex_str, nullptr, 16);
        //cout << hex_num;

        //保留一位小数
        double d_num = 1.23;
        cout << fixed << setprecision(1) << d_num;

        return 0;
	}
    {
        int num = 64;
        string num_str = bitset<32>(num).to_string();
        //cout << num_str;
    	bitset<32>bs(num_str);
        uint64_t num_bs = bs.to_ulong();
        cout << num_bs;

        return 0;
    }
	{
        int g_size;
        cin >> g_size;
        cin.ignore();

        vector<string>str_vec(g_size);
        for (int i=0; i<g_size; i++)
        {
            string input;
            getline(cin, input);

            string str_item;
            stringstream oh_sstream(input);
            string token;
            while (getline(oh_sstream,token,','))
            {
                str_item += token;
            }
            str_vec[i] = str_item;
        }

        Solution13 solu(str_vec);

        return 0;
	}
	{
        int g_size;
        cin >> g_size;
        cin.ignore();

        vector<vector<int>>grid(g_size);

        for (int r=0; r<g_size; r++)
        {
            vector<int>item;
            string input;
            getline(cin, input);
            stringstream oh_sstream(input);
            string token;
            while (getline(oh_sstream, token, ','))
            {
                item.push_back(stoi(token));
            }
            grid[r] = item;
        }

        Solution03 solu(grid);

        return 0;
	}
	{
        string input;
        getline(cin, input);

        vector<int>num_vec;
        stringstream oh_sstream(input);
        string token;
        while (getline(oh_sstream,token,','))
        {
            num_vec.push_back(stoi(token));
        }

        int limit;
        cin >> limit;

        Solution02 solu(num_vec, limit);
        return 0;
	}
    long long num;
    cin >> num;
    Solution01 solu(num);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
